//
// Created by 麻再挺 on 2021/12/17.
//

#include "dbf_tree.h"

/**
 * 深度搜索生成树
 * @param g 图
 * @param idx 索引
 * @param p 树
 */
void DFSTree(SMGraph g, int idx, CSTree *t);

/**
 * 广度优先生成树
 * @param g 图
 * @param idx 索引
 * @param p 树
 */
void BFSTree(SMGraph g, int idx, CSTree *t);

void DFSForest(SMGraph g, CSTree *t) {
    // 将要标记的数组初始化为false
    for (int i = 0; i < g.vexNum; ++i) {
        visited[i] = false;
    }
    CSTree q = NULL;
    // 遍历每个结点作为初始结点, 建立深度优先搜索树
    for (int i = 0; i < g.vexNum; ++i) {
        // 如果该顶点被标记为 false, 说明未被访问过
        if (!visited[i]) {
            // 创建一个新结点, 表示该顶点 必须使用结构体名称
            CSTree p = malloc(sizeof(CSNode));
            // 设置数据
            p->data = g.vex[i];
            p->firstChild = NULL;
            p->nextSibling = NULL;
            // 如果树为空,则作为树的树根
            if (!(*t)) {
                *t = p;
            } else {
                // 否则该顶点作为树根的兄弟结点
                q->nextSibling = p;
            }
            // 每次都要把q指针指向新的结点
            q = p;
            // 以该结点为起始结点, 构造深度优先生成树
            DFSTree(g, i, &p);
        }
    }
}

void DFSTree(SMGraph g, int idx, CSTree *t) {
    // 将正在访问的该顶点标志位设置为 true
    visited[idx] = true;
    // 设置是否为第一个孩子
    bool first = true;
    CSTree q = NULL;
    // 依次遍历该顶点的所有邻接点
    for (int i = FirstAdjVex(g, idx); i >= 0; i = NextAjdVex(g, idx, i)) {
        // 如果还未访问则访问结点
        if (!visited[i]) {
            //为该邻接点初始化为结点
            CSTree tmp = (CSTree) malloc(sizeof(CSNode));
            // 赋值
            tmp->data = g.vex[i];
            tmp->firstChild = NULL;
            tmp->nextSibling = NULL;
            // 该结点的第一个邻接点作为孩子结点
            if (first) {
                // 赋值孩子结点
                (*t)->firstChild = tmp;
                first = false;
            } else {
                // 否则为兄弟结点
                q->nextSibling = tmp;
            }
            // 保持最新
            q = tmp;
            // 循环查找
            DFSTree(g, i, &tmp);
        }
    }
}

void PreOrderCSTraverse(CSTree t) {
    if (t) {
        printf("%d ", t->data);
        PreOrderCSTraverse(t->firstChild);
        PreOrderCSTraverse(t->nextSibling);
    }
}

void BFSForest(SMGraph g, CSTree *t) {
    // 将要标记的数组初始化为false
    for (int i = 0; i < g.vexNum; ++i) {
        visited[i] = false;
    }
    CSTree q = NULL;
    // 遍历每个结点作为初始结点, 建立深度优先搜索树
    for (int i = 0; i < g.vexNum; ++i) {
        // 如果该顶点被标记为 false, 说明未被访问过
        if (!visited[i]) {
            // 创建一个新结点, 表示该顶点
            CSTree p = malloc(sizeof(CSNode));
            // 设置数据
            p->data = g.vex[i];
            p->firstChild = NULL;
            p->nextSibling = NULL;
            // 如果树为空,则作为树的树根
            if (!(*t)) {
                *t = p;
            } else {
                // 否则该顶点作为树根的兄弟结点
                q->nextSibling = p;
            }
            // 每次都要把q指针指向新的结点
            q = p;
            //以该结点为起始点，构建广度优先生成树
            BFSTree(g, i, &p);
        }
    }
}

void BFSTree(SMGraph g, int idx, CSTree *t) {
    CSTree p;
    // 初始化队列
    LinkQueue q;
    Link_Queue_Init(&q);
    // 将根节点入队
    Link_Queue_Enter(&q, (*t));
    // 当队列为空时证明遍历完成
    while (!Link_Queue_Empty(&q)) {
        // 判断是否为第一个结点
        bool first = true;
        // 对队首出队
        QElemType tmp;
        Link_Queue_Deter(&q, &tmp);
        p = (CSTree) tmp;
        // 判断结点中的数据在数组中的具体位置
        int num = LocateSVex(&g, p->data);
        // 设置已访问
        visited[idx] = true;
        // 遍历以出队结点为起始点的所有邻接点
        for (int i = FirstAdjVex(g, idx); i >= 0; i = NextAjdVex(g, num, i)) {
            //标志位为false，证明未遍历过
            if (!visited[i]) {
                //新建一个结点 p，存放当前遍历的顶点
                CSTree tp = (CSTree) malloc(sizeof(CSNode));
                tp->data = g.vex[i];
                tp->firstChild = NULL;
                tp->nextSibling = NULL;
                // 当前结点入队
                Link_Queue_Enter(&q, tp);
                // 更改标志位
                visited[i] = true;
                // 如果是出队顶点的第一个邻接点，设置p结点为其左孩子
                if (first) {
                    p->firstChild = tp;
                    first = false;
                }
                // 否则设置其为兄弟结点
                else {
                    p->nextSibling = tp;
                }
                // 赋值前一结点
                p = tp;
            }
        }
    }

}













